package cn.zhl.algorithm._5_递归;

/**
 * @program: demos
 * @description: 8皇后剪枝，回溯
 * @author: 刘振华
 * @create: 2020-07-14 16:01
 **/
public class Queens {
	private int[] cols; //从0开始，下标表示第几行，值表示第几列被占用了
	public Queens(int n){
		cols = new int[n];
	}
	public void result(){
		if(cols.length<1){
			return;
		}
		place(0);
	}

	private void place(int row){
		if(row>=cols.length){
			show();
			return;
		}
		for(int col = 0;col < cols.length;col++){
			boolean valid = valid(row, col);
			System.out.println("["+row+"]["+col+"] = "+valid);
			if(valid){
				cols[row] = col+1;
				place(row+1);
			}
		}
	}
	//该点是否是可以使用的
	private boolean valid(int row,int col){
		if(row == 0) {
			return true;
		}
		col++;
		for(int i = 0;i< row ;i++){
			if(col == cols[i] ||
				col == cols[i]+(row-i) ||
				col == cols[i]-(row -i)){
				return false;
			}
		}
		return true;
	}
	private void show(){
		for(int i = 0;i < cols.length; i++){
			System.out.print(cols[i]+",");
		}
		System.out.println();
		System.out.println("=================================");
	}
}
